#include "SortAlgorithms.h"

void CountingSort::Sort(int *inputArray, int *sortedArray, int maxValue, int inputSize)
{
  
  //initialize the space for the array that will contain the counts. we use maxValue + 1 because
  //maxValue is the index of the last array element we will reference
  int *countsArray = new int[maxValue + 1];
 
  //set all the counts to 0
  for(int i = 0; i <= maxValue; i++)
  {
    countsArray[i] = 0;
  }
  
  //each index of the counts array refers to a value from the inputArray
  //we go through the inputArray and count how many times each element is encountered
  //we store that count at the location with index equal to the value of the element of the inputArray
  //inside the countsArray
  for(int i = 0; i < inputSize; i++ )
  {
    countsArray[inputArray[i]] = countsArray[inputArray[i]] + 1;
  }
  
  //now we go through the counts array and we count the number of elements that are less than or equal to each value
  //this is accomplished by summing the count of each value with the count of the previous value from the countsArray
  //we go from 0 to the end, that's why the counts are accurate
  for(int i = 1; i <= maxValue; i++ )
  {
      countsArray[i] = countsArray[i] + countsArray[i - 1];
  }
  
  //now go from the end of the inputArray to 0 and position the value of
  //each element from the inputArray at the location where there were 
  //that many elements less than or equal to the element (the count taken from the countsArray)
  //inside the sortedArray.(the location is inside the sortedArray); however since we are
  //using a 0-based language if the count is x we will position the element at x-1 to account
  //for the 0th index. after we position the element in its correct position inside the sortedArray
  //we will decrease the number of elements inside countsArray that are <= to the element with 1
  for(int i = inputSize - 1; i >= 0; i --)
  {
    sortedArray[countsArray[inputArray[i]] - 1] = inputArray[i];
    countsArray[inputArray[i]] = countsArray[inputArray[i]] - 1;
  }
  
  //free the allocated memory for the countsArray
  delete []countsArray;
  return;
}